package com.steve.combat.algorithm.douyin;

/**
 * @Author: STEVE
 * @Description: 递归解决兔子繁殖问题
 * 这个问题实际上就是著名的斐波那契数列(Fibonacci sequence)：
 * <p>
 * 第1个月：1对兔子（刚出生）
 * <p>
 * 第2个月：1对兔子（还没成熟）
 * <p>
 * 第3个月：2对兔子（原来的1对+新生的1对）
 * <p>
 * 第4个月：3对兔子（原来的1对+上个月新生的1对又生1对）
 * <p>
 * 第5个月：5对兔子
 * <p>
 * ...
 * <p>
 * 递推关系：f(n) = f(n-1) + f(n-2)
 * @since: 2025-04-18
 */
public class RabbitRecursion {

    /**
     * 递归解决
     * 时间复杂度：O(2^n) - 指数级
     * 空间复杂度：O(n) - 调用栈深度
     */
    public static int fibonacciRecursive(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }

}
